package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/8 10:18
 **/
public class LongestValidParentheses32 {
    public int longestValidParentheses(String s) {
        if(s.isEmpty()) {
            return 0;
        }

        int left = 0;
        int right = 0;
        int maxLength = 0;
        // 先从左括号开始
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i) == '('){
                left++;
            } else {
                right++;
            }

            if(left == right) {
                maxLength = Math.max(maxLength, left+right);
            }
            // 右括号大从0开始
            if(right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        // 再反过来，从右括号开始算一边
        for(int j=s.length()-1;j>=0;j--) {
            if(s.charAt(j) == '('){
                left++;
            } else {
                right++;
            }

            if(left == right) {
                maxLength = Math.max(maxLength, left+right);
            }
            if(right < left) {
                left = right = 0;
            }
        }

        return maxLength;
    }
}
